Redistribution in Online Mechanisms
Victor Naroditskiy, Sofia Ceppi, Valentin Robu, Nicholas R. Je
nnings
School of Electronics and Computer Science
University of Southampton, UK
{vn,sc11v,vr2,nrj}@ecs.soton.ac.uk
ABSTRACT
Following previous work on payment redistribution in static mech-
anisms, we develop the theory of redistribution in online mech-
anisms (e.g., [2, 10, 8]). In static mechanisms, redistribution is
important as it increases social welfare in scenarios with no resid-
ual claimant. Many online scenarios also do not have a natural
residual claimant, and redistribution there is equally important. In
this work, we adopt a fundamental online mechanism design model
where a single expiring item is allocated in each of
T
periods.
Agents with unit demand are present in the market between their
arrival and departure periods, which are private information along
with the value an agent attributes to the item. For this model, we
derive a number of properties characterizing redistribution in on-
line mechanisms (including revenue monotonicity properties, and
quantifying the effect an agent can have on the total revenue). We
then design two redistribution functions. The first one generalizes
the static redistribution proposed by Cavallo [2] making redistri-
bution after the departure of the last agent. For this redistribution
function we provide theoretical worst-case guarantees. The sec-
ond function is truly “online” making redistribution to each agent
on her departure. The performance of both functions is evaluated
using numerical simulations.
1. INTRODUCTION
Revenue redistribution is a growing area of study within mecha-
nism design. Its importance can be intuitively illustrated by means
of a simple example. Consider a situation in which a number of
identical items need to be allocated among a group of agents (spe-
cific examples might include allocating free tickets for a popular
talk, deciding which roommate gets to use the living room for a
weekend party, or allocating university parking spots among fac-
ulty members). Each agent has a private value for the item, and we
would like to distribute the items in a way that maximizes social
welfare. In order to incentivize agents to reveal their private values,
payments must be introduced. Importantly, there is no revenue-
maximizing auctioneer or
residual claimant
to absorb the revenue.
Thus, any revenue collected represents the cost of truthfulness, and
decreases the social welfare. It has been shown [6] that the cost
cannot be zero: i.e., budget balance and allocative efficiency are
not compatible. Against this background, the redistribution litera-
ture aims to distribute back as much of the revenue as possible.
Much of the work on redistribution mechanisms focuses on find-
Appears in:
Proceedings of the 12th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS 2013), Ito,
Jonker, Gini, and Shehory (eds.), May, 6–10, 2013, Saint Paul, Min
-
nesota, USA.
Copyright
c
2013, International Foundation for Autonomous Agents and
Multiagent Systems (www.ifaamas.org). All rights reserved.
ing the best mechanism from the Groves class: i.e., on redistribut-
ing VCG payments (e.g., [10, 8, 11]). But some work has ad-
dressed non-efficient mechanisms [7, 4]. However, with the excep-
tion of [3] discussed in Section 7, all of the redistribution results
assume static settings, in which the decisions are made at the same
time in the presence of all participating agents. While relevant to
some settings, in others like electric vehicle charging and allocation
of computational resources in cloud computing this is not a suitable
model.
To this end, we provide the first results on redistribution in
online
mechanisms. Specifically, we consider the case in which decisions
must be made over time, with a separate decision made each period,
and agents who arrive and depart at various times not known by the
mechanism, i.e., the private information of each agent also includes
her arrival and departure times.
As in the prior work on static models, our goal is to maximize
social welfare. Welfare maximization is a natural objective for al-
locating resources in situations without a revenue-maximizing auc-
tioneer. An example of an online setting where social welfare is the
right objective is electric vehicle charging [5, 14], where vehicles,
arriving and departing at different times of day, draw electricity
from a shared resource such as a community-owned wind turbine
or need to divide between them a joint quota made available by the
electricity distribution company. Another example is cloud com-
puting, in which computational jobs arriving over time need to be
allocated to a number of processors.
In our work we consider the fundamental model where identical
items are distributed among agents with unit demand [13]. In par-
ticular, we focus on deterministic, individually rational (i.e., each
agent should not be worse off after participating in the mechanism),
and weakly budget-balanced (i.e., the total payment collected from
the agents should be non-negative) mechanisms where truthful re-
porting is a dominant strategy. We refer to the latter property as
dominant strategy incentive compatibility
(DSIC). A class of online
mechanisms satisfying these properties has been described in [13],
and we study redistribution within this class. This simple model
proves to be a good departure point for the study of redistribution
in online mechanisms. The model includes the properties specific
to online settings such as: (i) arrival and departure times are private
information of the agents, (ii) in each period no information about
agents arriving in the future is available, and (iii) the allocation de-
cisions in each period are interdependent. We start with deriving a
number of general properties for this online setting (see Section 3).
Based on the general properties, we design two redistribution
functions. One is a generalization of the function proposed for
static settings by Cavallo [2]. Under this rule, redistribution oc-
curs only after the last agent departs. We provide analytical guar-
antees of the performance of the generalized redistribution. The
second function we design, redistributes to each agent on her de-
parture. Performance of both functions is evaluated in numerical
simulations.
In summary, the main contributions of this work are as follows:
•
We derive general results characterizing properties of redis-
tribution functions in online domains that are required to guar-
antee dominant strategy truthfulness and weak budget bal-
ance.
•
Based on these general properties, we design two redistribu-
tion functions for online settings: one that redistributes to all
agents at the last period, and one that redistributes to each
agent at her departure time. Moreover, we provide theoreti-
cal guarantees on the performance of the first redistribution
function.
•
We evaluate the performance of both functions in redistribut-
ing collected revenue using numerical simulations.
The remainder of the paper is organized as follows. First, we de-
scribe the online mechanism design model we adopt from [13]. We
proceed with a series of results pointing out the features that an on-
line redistribution function must satisfy to guarantee weak budget
balance and DSIC. Then, we propose two redistribution functions
analyzing them in terms of the percentage of revenue redistributed.
Finally, we present the results of numerical simulations of the func-
tions described.
2. MODEL OF ONLINE MECHANISMS
Existing literature on online mechanism design discusses several
models of online allocation (see [13] for an overview). We fo-
cus on a fundamental model proposed in [9, 13]. Specifically, we
study the class of
deterministic, model-free
online mechanisms. In
such mechanisms, the allocation rule itself is deterministic, and the
mechanism does not need a model of future arrivals of the agents
in order to compute the allocation. Furthermore, in this work we
only consider online mechanisms where truthtelling (i.e., true re-
porting of types by the agents) is a dominant strategy. Determin-
istic, model-free, dominant-strategy mechanisms are the most de-
sirable mechanisms to design as they require no prior information
on agents’ types, and do not make any assumptions about risk-
preferences of the agents.
Formally, there are
T
discrete time periods, and agents may ar-
rive and depart within
[1
, T
]
. There is an identical item available
for allocation in each period.
1
The items are “expiring", and if
not allocated within their period, they disappear (this is natural, for
example, when items correspond to computational time on a ma-
chine). We define the type of agent
i
as
θ
i
= (
a
i
, d
i
, v
i
)
, where
a
i
is her arrival period,
d
i
is her departure period (
1
≤
a
i
≤
d
i
≤
T
),
and
v
i
∈
R
is her value for obtaining the item. We sometimes
refer to the interval
[
a
i
, d
i
]
when agent
i
is present as agent
i
’s
ac-
tive window
. We use
N
to denote the set of agents that are present
at some time between
1
and
T
, with the cardinality denoted by
n
=
|
N
|
. We denote
2
by
π
t
:
θ
→ {
0
,
1
}
n
the
greedy
allocation
function [13] that, at each time
t
, allocates the good to the previ-
ously unallocated agent who is present at time
t
and has the highest
1
The case of multi-unit supply per period is not discussed in this
paper, but our model can be extended to cover this case.
2
To avoid complicated notation, we use types
θ
of all agents
N
as
an argument to the allocation function
π
and of all agents except
i
,
N
\
i
, to the payment function
x
i
. However, allocation at period
t
is decided based only on the types of the agents that already arrived
in the market. The types of agents that have not yet arrived are not
used (and, in fact, cannot be known) by these functions.
value among all unallocated agents present at
t
. Allocation to agent
i
is specified by
π
t
i
(
θ
)
∈{
0
,
1
}
.
The utility agent
i
∈
N
obtains from participating in the market
is:
u
i
(
θ
) =
v
i
π
i
(
θ
)
−
x
i
(
θ
)
where
x
i
(
θ
)
denotes the payment of agent
i
(defined in Equation 1
and generalized in Equation 3), and
π
i
(
θ
)
, defined as
P
d
i
t
=
a
i
π
t
i
(
θ
)
indicates whether agent
i
has been allocated (
π
i
(
θ
) = 1
) or not
(
π
i
(
θ
) = 0
).
We remark that, for this deterministic, single-unit demand set-
ting, the state of the art characterization was first presented by
Hajiaghayi
et al.
[9] (and, in a more extended form, by Parkes
[13]). Assuming individual rationality and zero payment from un-
allocated agents, they show that the allocation function
π
t
can be
truthfully implemented in single-valued domains with
limited mis-
reports
3
(i.e., no early arrivals/late departures can be reported) if
and only if the payment
x
i
of each agent
i
∈
N
takes the form:
x
i
(
θ
) = ˆ
x
i
(
θ
) =
(
v
c
(
θ
−
i
, a
i
, d
i
)
if
π
i
(
θ
) = 1
0
otherwise
(1)
where
v
c
(
θ
−
i
, a
i
, d
i
)
denotes the
critical value
of agent
i
that is
defined as:
v
c
(
θ
−
i
, a
i
, d
i
) = min
v
′
i
∈
R
v
′
i
s.t.
π
i
(
θ
′
i
, θ
−
i
) = 1
, for
θ
′
i
= (
v
′
i
, a
i
, d
i
)
(2)
We dispose of the assumption that unallocated agents’ payment
is zero, and characterize all possible ways to modify the payment
function above.
x
i
(
θ
) = ˆ
x
i
(
θ
)
−
h
(
θ
−
i
, a
i
, d
i
)
(3)
where
h
(
θ
−
i
, a
i
, d
i
)
is the redistribution agent
i
receives.
In the next section we discuss how redistribution should be de-
fined in order for the allocation mechanism to maintain DSIC and
weak budget balance. Note that, individual rationality—the prop-
erty that each agent has a non-negative utility—is satisfied by the
mechanism described above if and only if the redistribution is non-
negative. This will be the case throughout the paper.
The last part of the model that needs to be specified is the evalu-
ation metric. As in much of the work on the static case (e.g., [2, 10,
8]), we evaluate mechanisms based on the worst-case performance
guarantee: i.e., the welfare that is guaranteed regardless of agents’
private information.
In order to better explain our results, we benchmark them against
the existing results for the static case. The relevant static case is
allocating
m
identical items among
n
agents (by definition, there
is only one period
T
= 1
in the static case). Note that in the online
case, since we consider the scenario with single unit supply (i.e.,
only one item can be allocated in each time interval), the number
of items is the same as the number of periods
m
=
T
.
The worst-case ratio for allocating
m
items among
n
agents is
measured as the percentage of revenue that is guaranteed to be re-
distributed back to the agents regardless of their types:
r
(
m, n
) = min
θ
H
(
θ, m, n
)
R
(
θ, m, n
)
(4)
where
R
(
θ, m, n
)
is the collected revenue, and
H
(
θ, m, n
) =
X
i
∈
N
h
(
θ
−
i
)
3
We adopt this assumption throughout the paper.